package MyGreed;

import java.util.Arrays;

/**
 * 1402. 做菜顺序
 *
 * 一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。
 *
 * 一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。
 *
 * 请你返回做完所有菜 「喜爱时间」总和的最大值为多少。
 *
 * 你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。
 *
 *
 *
 * 示例 1：
 *
 * 输入：satisfaction = [-1,-8,0,5,-9]
 * 输出：14
 * 解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。
 */


/**
 * 方法一：贪心算法
 *
 * 分析
 *
 * 我们从最简单的情况开始思考起。
 *
 * 假设我们只能选一道菜，那么我们应该如何选择呢？显然，选择满意程度最大的那一道菜 s0s_0s0​ 是最优的，并且我们需要验证是否有 s0>0s_0 > 0s0​>0，因为如果 s0≤0s_0 \leq 0s0​≤0，我们选择这道菜不会有任何受益。
 *
 * 现在我们可以再多选一道菜，也就是两道菜，那么我们应该如何选择呢？假设我们选择了 s1s_1s1​ 这道菜，那么满意程度的总和为
 *
 * s1+2s0s_1 + 2s_0 s1​+2s0​
 *
 * 由于 s0s_0s0​ 是满意程度最大的那道菜，我们要最大化上述表达式的值，就应该找到尽可能大的 s1s_1s1​。因此在最优的情况下，我们选择满意程度次大的那一道菜作为 s1s_1s1​，并且需要保证选择之后的收益多于选择之前的收益，即
 *
 * s1+2s0>s0s_1 + 2s_0 > s_0 s1​+2s0​>s0​
 *
 * 也就是只要满足
 *
 * s1+s0>0s_1 + s_0 > 0 s1​+s0​>0
 *
 * 我们就可以选择 s1s_1s1​。
 *
 * 对于第三道菜也是如此，我们如果要选择 s2s_2s2​，就应该选择满意程度第三大的那一道菜作为 s2s_2s2​，同时要保证收益的增加，即
 *
 * s2+2s1+3s0>s1+2s0s_2 + 2s_1 + 3s_0 > s1 + 2s_0 s2​+2s1​+3s0​>s1+2s0​
 *
 * 也就是当
 *
 * s2+s1+s0>0s_2 + s_1 + s_0 > 0 s2​+s1​+s0​>0
 *
 * 时，我们就可以选择 s2s_2s2​。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/reducing-dishes/solution/zuo-cai-shun-xu-by-leetcode-solution/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */

/**
 * 每加一次要加上 * time+1
 */
public class Leetcode1402 {
    public static int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int len = satisfaction.length;

        if(len <= 0){
            return 0;
        }

        int res = 0; // 累计值
        int sum = 0; // 当前值
        for(int i=len-1;i>=0;i--){
            if(sum + satisfaction[i] > 0){
                sum += satisfaction[i];
                res += sum;
            }else{
                break;
            }
        }
        return res;
    }
}
